package com.kobe.algorithm.leetcode.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ：caopengfei
 * @date ：2021/2/26
 */
public class Demo2 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int n = candidates.length;
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        for (int first = 0; first < n ; first++) {
            if(first>0 && candidates[first] == candidates[first-1] ){
                continue;
            }
            combinationSum2(result,candidates,first, n-1,target);
        }
        return result;
    }

    private List<Integer> combinationSum2(List<List<Integer>> resultList,int [] nums,int start,int end,int target){
        List<Integer> result = new ArrayList<>();
        if(nums[start] > target){
            return result;
        }
        while(start < end){
            if(nums[start] >= target ){
                break;
            }else if( nums[start]+nums[end] > target){
                --end;
            }else if(nums[start]+nums[end]  < target ||  (start>0 && nums[start] ==  nums[start-1])){
                start++;
            }else{
                result.add(nums[start]);
                result.add(nums[end]);
                resultList.add(result);
                List<Integer> group = combinationSum2(resultList,nums,start+1,end-1,nums[end]);
                if(!group.isEmpty()){
                    group.add(0,result.get(0));
                    resultList.add(group);
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
       int [] nums = {10,1,2,7,6,1,5};
        int [] nums1 = {1,1,2,5,6,7,10};
        Demo2 demo2 = new Demo2();
        System.out.println(demo2.combinationSum2(nums,8));

    }

}
